package ACWing.SearchAndGraphTheory.最短路;
//849. Dijkstra求最短路 I   朴素版的适用与稠密图即边比点大的多

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author :chenjie
 * @date :Created 2022/12/26 21:55
 */

/**
 * 贪心思想
 * 从未访问的点中找出当前与我最短距离的点并更新这个点到其他点的距离选取最小值来进行存储，所以最后到n点肯定是最短的距离
 */
public class Dijkstra1 {
    static int n,m;
    static int[][]arr=new int[510][510];
    static int[]dist=new int[510];//到i点的距离
    static boolean[]st=new boolean[510];
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        for (int i = 0; i < n; i++) {
            Arrays.fill(arr[i],(int)1E9);
        }
        for (int i = 0; i < m; i++) {
            int a=sc.nextInt();
            int b=sc.nextInt();
            int t=sc.nextInt();
            arr[a][b]=Math.min(arr[a][b],t);
        }
        System.out.println(dijkstra());

    }
    public static int dijkstra(){
        Arrays.fill(dist,(int)1E9);
        dist[1]=0;
        for (int i = 0; i < n; i++) {
            int t=-1;
            for (int j = 1; j <= n; j++) {
                if(!st[j]&&(t==-1||dist[t]>dist[j])){
                    t=j;
                }
            }
            st[t]=true;
            for (int j = 1; j <= n; j++) {
                dist[j]=Math.min(dist[j],arr[t][j]+dist[t]);
            }
        }
        if(dist[n]==(int)1E9){
            return -1;
        }
        return dist[n];
    }
}
